Codeforces Round #519 (A-F)

发表于 | 更新于 | 分类于 | 阅读次数：

水一把 CF，感觉全暴力而且代码量略少。

G 题不会..打扰了..

地址

A. Elections

公式解即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, a[N];
int main() {
    scanf("%d", &n);
    int s = 0, k = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s += a[i];
        k = max(k, a[i]);
    }
    k = max(k, s*2/n+1);
    printf("%d\n", k);
}

B. Lost Array

KMP 的 next 函数求出所有循环节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int n, a[N], nxt[N];
void GetNxt(int s[], int n) {
	int j = 0, k = -1;
	nxt[0] = -1;
	while(j < n) {
		if (k != -1 && s[j] != s[k]) k = nxt[k];
		else nxt[++j] = ++k;
	}
}
vector<int> ans;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = n; i >= 1; i--) a[i] -= a[i-1];
	GetNxt(a+1, n);
	int m = n;
	while (nxt[m] >= 0) {
		ans.push_back(n-nxt[m]);
		m = nxt[m];
	}
	printf("%d\n", ans.size());
	for (int i = 0; i < ans.size(); i++) {
		printf("%d", ans[i]);
		if (i == ans.size()-1) puts("");
		else printf(" ");
	}
}

C. Smallest Word

题意

给定一个只有字符 a,b 的串，问按顺序 reverse 哪几个前缀可以使其字典序最小。

分析

转几次就会发现所有的 a 和所有的 b 是可以转到一起的，故先转到一起，最后转到 a 在前 b 在后即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
char s[N];
bool val[N];
int main() {
    scanf("%s", &s);
    int n = strlen(s);
    char now = s[0];
    for (int i = 0; i < n; i++) {
        if (s[i] != now) {
            val[i-1] = 1;
            now = s[i];
        }
    }
    if (now == 'a') val[n-1] = 1;
    for (int i = 0; i < n; i++) {
        printf("%d", val[i]);
        if (i == n-1) puts("");
        else printf(" ");
    }
}

D. Mysterious Crime

题意

给定10个排列，问它们的相同子串的个数。

分析

由于是排列，故每个数字唯一双射一个位置。

可直接按第一个串的子串找，相当于把第一个串分成好多段，每一段都是一个相同子串，由此计数。

具体分法，即某一段是否在某个位置结束，只用看第一段这个位置和其他串的对应位置是否映射同一个数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int n, m;
int a[11][N], pos[11][N];
bool vis[N];
bool check(int x, int cnt) {
    for (int i = 1; i <= m; i++)
        if (pos[i][x]+cnt > n) return 0;
    for (int i = 2; i <= m; i++)
        if (a[i][pos[i][x]+cnt] != a[i-1][pos[i-1][x]+cnt]) return 0;
    return 1;
}
int main() {
    scanf("%d%d",&n, &m);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
            pos[i][a[i][j]] = j;
        }
    if (m == 1) {
        printf("%lld\n",1ll*n*(n+1)/2);
        return 0;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        while(check(a[1][i], cnt)) cnt++;
        ans += 1ll*cnt*(cnt+1)/2;
        i += cnt-1;
    }
    printf("%lld\n", ans);
}

D - Crossing

题意

给定 n 个 (x,y) ，两两匹配的贡献是\(min(a_x+b_y,a_y+b_x)\)

然后除掉给定的m对匹配后，问你剩余的两两匹配之和。

分析

按 \(a_x+b_y<a_y+b_x\) 即 \(a_x-a_y<b_x-b_y\) 排序后直接算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+5;
int n, m;
struct Node {
    int x, y, id;
    bool operator < (const Node b) const {
        return x-y < b.x-b.y;
    }
}a[N];
ll x[N], y[N];
ll ans[N];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].id = i;
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        int res = min(a[u].x+a[v].y, a[u].y+a[v].x);
        ans[u] -= res;
        ans[v] -= res;
    }
    sort(a+1, a+1+n);
    for (int i = 1; i <= n; i++) x[i] = x[i-1] + a[i].x;
    for (int i = n; i >= 1; i--) y[i] = y[i+1] + a[i].y;
    for (int i = 1; i <= n; i++) {
        ans[a[i].id] += 1ll*a[i].y*(i-1)+x[i-1];
        ans[a[i].id] += 1ll*a[i].x*(n-i)+y[i+1];
    }
    for (int i = 1; i <= n; i++) {
        printf("%lld", ans[i]);
        if (i == n) puts("");
        else printf(" ");
    }
}

F. Make It One

题意

从 n(3e5) 个给定的数字中选一组 gcd 为 1 的数，最少选几个

分析

根据唯一分解定理，每选择一个数字至少消去一种素因子，而前 7 个素因子之积已超过 3e5，故至多选7个。

\(dp[i][j]\) 表示 i 的倍数中选出 j 个，且 gcd 为 i 的方案数 ：

$$dp[i][j] = \binom{cnt_i}{j}-\sum_{k=2}^{\infty}dp[i*k][j]$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+5;
const int MOD = 1e9+7;
int F[N], Finv[N], inv[N];
void init() {
	inv[1] = 1;
	for (int i = 2; i < N; i ++) {
		inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
	}
	F[0] = Finv[0] = 1;
	for (int i = 1; i < N; i ++) {
		F[i] = F[i-1] * 1ll * i % MOD;
		Finv[i] = Finv[i-1] * 1ll * inv[i] % MOD;
	}
}
int comb(int n, int m) {
	if (m < 0 || m > n) return 0;
	return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;
}
int n, cnt[N];
ll dp[N][10];
int main() {
    init();
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int x; scanf("%d", &x);
		cnt[x]++;
	}
	for (int i = 1; i < N; i++)
		for (int j = i+i; j < N; j += i)
			cnt[i] += cnt[j];
	for (int i = N-1; i >= 1; i--) {
		for (int j = 1; j <= 7; j++) {
			dp[i][j] = comb(cnt[i], j);
			for (int k = i+i; k < N; k += i)
				dp[i][j] = (dp[i][j] + MOD - dp[k][j]) % MOD;
		}
	}
	int ans = -1;
	for (int i = 7; i >= 1; i--) if (dp[1][i]) ans = i;
	printf("%d\n", ans);
}